public class MoreThanHalf {
    public static void main(String[] args) {
        int[] arr = {1,2,3,2,2,2,5,4,2};
        System.out.println(majorityElement(arr));
    }
    public static boolean checkInvalidArray(int[] arr){
        //检查是否为无效数据
        boolean g_bInputInvalid = false;
        if(arr == null || arr.length <= 0) {
            g_bInputInvalid = true;
        }
        return g_bInputInvalid;

    }
    public static boolean checkMoreThanHalf(int[] arr,int number){
        //检查出现次数最多的那个数字是否大于1/2数组长度
        int times = 0;
        for(int i=0;i<arr.length;++i) {
            if(arr[i] == number)
                times++;
        }
        boolean isMoreThanHalf = true;
        if(times * 2 <= arr.length) {
            isMoreThanHalf = false;
        }
        return isMoreThanHalf;
    }

    public static int majorityElement(int[] arr) {
        //找出现次数最多的
        if(checkInvalidArray(arr)){
            return -1;
        }
        int result = arr[0];
        int times = 1;
        for(int i=1;i<arr.length;++i) {
            if(times == 0) {
                result = arr[i];
                times = 1;
            }
            else if(arr[i] == result) {
                times++;
            }
            else {
                times--;
            }
        }
        if(!checkMoreThanHalf(arr,result)) {
            result = 0;
        }
        return result;
    }
}
